package Studing;


import java.util.Scanner;

/**
 * @ClassName AC01背包
 * @Description: TODO
 * @Author hl
 * @Date 2020/8/6
 * @Version V1.0
 **/
public class AC01背包 {
    public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int N=5;
    int W=50;
    int []weight={20,12,11,10,9};
    int []value={24,14,12,10,7};

        System.out.println(knapsack(W,N,weight,value));
    }
    public static int knapsack(int W, int N, int[] weights, int[] values) {
        int[] dp = new int[W + 1];
        for (int i = 1; i <= N; i++) {
            int w = weights[i - 1], v = values[i - 1];
            for (int j = W; j >= 1; j--) {
                if (j >= w) {
                    dp[j] = Math.max(dp[j], dp[j - w] + v);
                }
            }
        }
        return dp[W];
    }
}
